First, background art of the present invention and necessary terms to describe the present invention will be described.
A secret sharing scheme (Share, Reconst) is a protocol for sharing a secret a that a user holds with a plurality of server apparatuses 1 to N, and for holding the secret a. And, the secret sharing scheme (Share, Reconst) is composed from a share generation function Share that generates a “share” from the secret a and a reconstruction function Reconst that reconstructs the secret a from the “share”. In many cases including a scheme described in Non-Patent Literature 1 (NPL1), the secret a and the share are element of a finite field. In the present disclosure herein, a situation where the secret a and the share are elements of the finite field will be considered. In the following, the secret sharing scheme in such situation will be described.
Assumed that F is a finite field, secret sharing where the secret a and the share are elements of the finite field F is called “secret sharing in F”. In addition, the share generated by “secret sharing in F” is called “share of secret a over F” or “share of secret a in F”.
Inputs and outputs of the Share function and the Reconst function are as below.                The share generation function Share receives, as an input, the secret a, server apparatus number N, and the finite field F (or information regarding the finite field F), then, outputs the shares of the secret a s[1], . . . , s[N].        The reconstruction function Reconst receives, as an input, a part or whole of the shares s[1], . . . , s[N] and the finite field F (or the information regarding the finite field F), then, outputs the secret a or data indicating a “failure of reconstruction”.        
The secret sharing scheme (Share, Reconst) is used with the following procedures. First, when a user U shares the secret a with the server apparatuses 1 to N, the user U acquires shares s[1], . . . , s[N]∈F as output by executing the Share(a, N, F). Next, the user respectively transmits the shares s[1], . . . , s[N] to the server apparatuses 1 to N. In future, in a case where it is necessary to reconstruct from the secret from the share, server apparatuses i_1 to i_v that satisfy {i_1, . . . , i_v}∈Access transmit their own shares, s[i_1], . . . , s[i_v], to the user U. Next, the user U acquires the secret a by executing the Reconst (s[i_1], . . . , s[i_v], F).
In the above, a case where the user U executes the Reconst (s[i_1], . . . , s[i_v], F) has been described. It should be noted that, a user other than the user U or the server apparatus may execute the Reconst (s[i_1], . . . , s[i_v], F).
Further, when a group Access that is a subset of {1, . . . , N} satisfies the below, the group Access is called an access structure over {1, . . . , N}.                If S∈Access and S⊂T, then T∈Access        
In addition, when (Share, Reconst) satisfies the following characteristic, the (Share, Reconst) is called “Access safe”.                Assumed that s[1], . . . , s[N] are outputs of Share(a, N, F), and S={i_1, . . . , i_v} is a subset of {1, . . . , N}. In this case, if S∈Access, Reconst(s[i_1], . . . , s[i_v], F) outputs the secret a. On the other hand, if, S∈Access is not satisfied, any partial information of the secret a cannot be known from s[i_1], . . . , s[i_v].        